{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Increasing Order Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: increasingBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #递增顺序搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉搜索树的<meta charset=\"UTF-8\" />&nbsp;<code>root</code>&nbsp;，请你 <strong>按中序遍历</strong> 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/17/ex1.jpg\" style=\"height: 350px; width: 600px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,3,6,2,4,null,8,1,null,null,null,7,9]\n",
    "<strong>输出：</strong>[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/17/ex2.jpg\" style=\"height: 114px; width: 300px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,1,7]\n",
    "<strong>输出：</strong>[1,null,5,null,7]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数的取值范围是 <code>[1, 100]</code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [increasing-order-search-tree](https://leetcode.cn/problems/increasing-order-search-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [increasing-order-search-tree](https://leetcode.cn/problems/increasing-order-search-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,3,6,2,4,null,8,1,null,null,null,7,9]', '[5,1,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def increasingBST(self, root):\n",
    "        dummy = TreeNode(-1)\n",
    "        self.prev = dummy\n",
    "        self.inOrder(root)\n",
    "        return dummy.right\n",
    "    \n",
    "    def inOrder(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        root.left = None\n",
    "        self.prev.right = root\n",
    "        self.prev = root\n",
    "        self.inOrder(root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        dummy = TreeNode()\n",
    "        tail = dummy\n",
    "        \n",
    "        def zz(node: TreeNode):\n",
    "            if node is None:\n",
    "                return\n",
    "            nonlocal tail\n",
    "            zz(node.left)\n",
    "            node.left = None\n",
    "            tail.right = node\n",
    "            tail = node\n",
    "            zz(node.right)\n",
    "\n",
    "        zz(root)\n",
    "        return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        res = []\n",
    "        def dfs(node: TreeNode):\n",
    "            if not node:\n",
    "                return \n",
    "            dfs(node.left)\n",
    "            res.append(node.val)\n",
    "            dfs(node.right)\n",
    "\n",
    "        # 中序遍历记录下所有节点值\n",
    "        dfs(root)\n",
    "\n",
    "        # 重建二叉搜索树\n",
    "        sentinel = previous = TreeNode()\n",
    "        for val in res:\n",
    "            previous.right = TreeNode(val)\n",
    "            previous = previous.right\n",
    "\n",
    "        return sentinel.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:                \n",
    "        res=[]\n",
    "        def dfs(root,res):\n",
    "            if not root:\n",
    "                return []\n",
    "            if root.left:                \n",
    "                dfs(root.left,res)\n",
    "            res.append(root.val)\n",
    "            if root.right:\n",
    "                dfs(root.right,res)\n",
    "        dfs(root,res)\n",
    "        \n",
    "        rr=TreeNode(res.pop(0))\n",
    "        new=rr\n",
    "        while res:\n",
    "            t=TreeNode(res.pop(0))\n",
    "            new.right=t\n",
    "            new=t\n",
    "        return rr\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def inOrder(node):\n",
    "            if node.left:\n",
    "                inOrder(node.left)\n",
    "            node.left = None\n",
    "            self.prev.right = node\n",
    "            self.prev = node\n",
    "            if node.right:\n",
    "                inOrder(node.right)\n",
    "\n",
    "        dummy = TreeNode(-1)\n",
    "        self.prev = dummy\n",
    "        inOrder(root)\n",
    "        return dummy.right\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        left=self.increasingBST(root.left)\n",
    "        right=self.increasingBST(root.right)\n",
    "        root.left=None\n",
    "        root.right=right\n",
    "        if not left:\n",
    "            return root\n",
    "        p=left\n",
    "        while p and p.right:\n",
    "            p=p.right\n",
    "        p.right=root\n",
    "        return left\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def zz(node: TreeNode):\n",
    "            head = tail = node\n",
    "            if node.left:\n",
    "                head, lt = zz(node.left)\n",
    "                lt.right = node\n",
    "                node.left = None\n",
    "            if node.right:\n",
    "                rh, tail = zz(node.right)\n",
    "                node.right = rh\n",
    "            return (head, tail)\n",
    "        return zz(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def func(root):\n",
    "            if not root:\n",
    "                return None, None\n",
    "            l_h, l_t = func(root.left)\n",
    "            r_h, r_t = func(root.right)\n",
    "            if not l_h:\n",
    "                if not r_h:\n",
    "                    return root, root\n",
    "                root.right = r_h\n",
    "                return root, r_t\n",
    "            if not r_h:\n",
    "                l_t.right = root\n",
    "                root.left = None\n",
    "                return l_h, root\n",
    "            else:\n",
    "                l_t.right = root\n",
    "                root.left = None\n",
    "                root.right = r_h\n",
    "                return l_h, r_t\n",
    "        h, _ = func(root)\n",
    "        return h\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(r):\n",
    "            if not r:\n",
    "                return \n",
    "            dfs(r.left)\n",
    "            stack.append(r)\n",
    "            dfs(r.right)\n",
    "        \n",
    "        stack = []\n",
    "        dfs(root)\n",
    "        r = stack[0]\n",
    "        t = r \n",
    "        for i in range(1, len(stack)):\n",
    "            t.left = None\n",
    "            t.right = stack[i]\n",
    "            t = stack[i]\n",
    "        t.left, t.right = None, None\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        dummy = TreeNode(-1)\n",
    "        self.prev = dummy\n",
    "        self.inOrder(root)\n",
    "        return dummy.right\n",
    "        \n",
    "    def inOrder(self, root):\n",
    "        if not root:\n",
    "            return None\n",
    "        self.inOrder(root.left)\n",
    "        root.left = None\n",
    "        self.prev.right = root\n",
    "        self.prev = root\n",
    "        self.inOrder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        l = []\n",
    "\n",
    "        def dfs(root: TreeNode):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            l.append(root.val)\n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        res = TreeNode()\n",
    "        node = res\n",
    "        for num in l:\n",
    "            t =  TreeNode(val = num)\n",
    "            node.right = t\n",
    "            node = node.right\n",
    "        return res.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return []\n",
    "            return inorder(node.left)+[node]+inorder(node.right)\n",
    "\n",
    "        nodes = inorder(root)\n",
    "        dummy = TreeNode()\n",
    "        current = dummy\n",
    "\n",
    "        for node in nodes:\n",
    "            current.right = node\n",
    "            current = node\n",
    "            node.left = None\n",
    "        \n",
    "        return dummy.right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        res=[]\n",
    "        self.dfs(root,res)\n",
    "\n",
    "        new_root = TreeNode(res[0])\n",
    "        end = new_root\n",
    "        for i in res[1:]:\n",
    "            curnode=TreeNode(i)\n",
    "            end.right=curnode\n",
    "            end=curnode\n",
    "        return new_root\n",
    "        \n",
    "    \n",
    "    def dfs(self,node,res):\n",
    "        if node == None:return\n",
    "        self.dfs(node.left,res)\n",
    "        res.append(node.val)\n",
    "        self.dfs(node.right,res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def f(root):\n",
    "            if root:\n",
    "                l_small = r_large = root\n",
    "                if root.left:\n",
    "                    l_small, l_large = f(root.left)\n",
    "                    l_large.right = root\n",
    "                    root.left = None\n",
    "                if root.right:\n",
    "                    r_small, r_large = f(root.right)\n",
    "                    root.right = r_small\n",
    "                return l_small, r_large\n",
    "        ans = f(root)[0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.res = []\n",
    "        self.inorder(root)\n",
    "        if not self.res:\n",
    "            return\n",
    "        dummy = TreeNode(-1)\n",
    "        cur = dummy\n",
    "        for node in self.res:\n",
    "            node.left = node.right = None\n",
    "            cur.right = node\n",
    "            cur = cur.right\n",
    "        return dummy.right\n",
    "\n",
    "    def inorder(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inorder(root.left)\n",
    "        self.res.append(root)\n",
    "        self.inorder(root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        dummy = TreeNode(-1)\n",
    "        self.prev = dummy\n",
    "        self.inorder(root)\n",
    "        return dummy.right\n",
    "\n",
    "    def inorder(self,root):\n",
    "        if not root:\n",
    "            return None\n",
    "        self.inorder(root.left)\n",
    "        root.left = None\n",
    "        self.prev.right = root\n",
    "        self.prev = root\n",
    "        self.inorder(root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def inorderTraversal(r):\n",
    "            if not r:\n",
    "                return []\n",
    "            left = inorderTraversal(r.left)\n",
    "            ans = [r]\n",
    "            right = inorderTraversal(r.right)\n",
    "            return left + ans + right\n",
    "        \n",
    "        lst = inorderTraversal(root)\n",
    "        lst[-1].left = None\n",
    "        lst[-1].right = None\n",
    "        for i in range(len(lst) - 1):\n",
    "            lst[i].left = None\n",
    "            lst[i].right = lst[i + 1]\n",
    "        return lst[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST1(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        res = []\n",
    "        def process(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            \n",
    "            process(node.left)\n",
    "            res.append(node)\n",
    "            process(node.right)\n",
    "        \n",
    "\n",
    "        process(root)\n",
    "        dummy = TreeNode(-1)\n",
    "        cur = dummy\n",
    "        for n in res:\n",
    "            cur.right = TreeNode(n.val)\n",
    "            cur = cur.right\n",
    "        \n",
    "        return dummy.right\n",
    "\n",
    "    \n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        res = []\n",
    "        def process(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            nonlocal pre\n",
    "            process(node.left)\n",
    "            pre.right = node \n",
    "            node.left = None\n",
    "            pre = node\n",
    "            process(node.right)\n",
    "        \n",
    "        dummy = TreeNode(-1)\n",
    "        pre = dummy\n",
    "        process(root)\n",
    "        \n",
    "        return dummy.right\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode, ans = None) -> TreeNode:\n",
    "        if not root:\n",
    "            return ans\n",
    "        root.right = self.increasingBST(root.right, ans)\n",
    "        ans = self.increasingBST(root.left, root)\n",
    "        root.left = None\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def helper(root):\n",
    "    if not root: return None, None\n",
    "    l1, l2 = helper(root.left)\n",
    "    root.left = None\n",
    "    if l2: l2.right = root\n",
    "    root.right, r2 = helper(root.right)\n",
    "    return (l1 if l1 else root, r2 if r2 else root)\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        return helper(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        #传入子树的root节点，返回链表的起止节点\n",
    "        def dfs(root):\n",
    "            ret = [root, root]\n",
    "            if root.left:\n",
    "                (sLeft,lLeft) = dfs(root.left)\n",
    "                lLeft.right = root\n",
    "                ret[0] = sLeft\n",
    "                root.left = None\n",
    "            if root.right:\n",
    "                (sRight, lRight) = dfs(root.right)\n",
    "                root.right = sRight\n",
    "                ret[1] = lRight\n",
    "            return ret \n",
    "        \n",
    "        return dfs(root)[0]\n",
    "            \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        stack, ans = [], False\n",
    "        while root or stack:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            p = stack.pop()\n",
    "            if not ans:\n",
    "                res = TreeNode(p.val)\n",
    "                t = res\n",
    "                ans = True\n",
    "            else:\n",
    "                res.right = TreeNode(p.val)\n",
    "                res = res.right\n",
    "            root = p.right\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        dummy = TreeNode(-1)\n",
    "        self.prev = dummy\n",
    "        self.inOrder(root)\n",
    "        return dummy.right\n",
    "        \n",
    "    def inOrder(self, node):\n",
    "        if node.left:\n",
    "            self.inOrder(node.left)\n",
    "        node.left = None\n",
    "        self.prev.right = node\n",
    "        self.prev = node\n",
    "        if node.right:\n",
    "            self.inOrder(node.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.res=[]\n",
    "        self.inOrder(root)\n",
    "        if not self.res:\n",
    "            return\n",
    "        \n",
    "        dummy=TreeNode(-1)\n",
    "        cur=dummy\n",
    "        for node in self.res:\n",
    "            node.left=node.right=None\n",
    "            cur.right=node\n",
    "            cur=cur.right\n",
    "        return dummy.right   \n",
    "\n",
    "    def inOrder(self,root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        self.res.append(root)\n",
    "        self.inOrder(root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        res=[]\n",
    "        self.dfs(root,res)\n",
    "\n",
    "        new_root = TreeNode(res[0])\n",
    "        end = new_root\n",
    "        for i in res[1:]:\n",
    "            end.right=TreeNode(i)\n",
    "            end=end.right\n",
    "        return new_root\n",
    "        \n",
    "    \n",
    "    def dfs(self,node,res):\n",
    "        if node == None:return\n",
    "        self.dfs(node.left,res)\n",
    "        res.append(node.val)\n",
    "        self.dfs(node.right,res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root: return None \n",
    "        if not root.left and not root.right: return root \n",
    "        if not root.left and root.right:\n",
    "            root.right = self.increasingBST(root.right)\n",
    "            return root \n",
    "        if not root.right and root.left:\n",
    "            cur = pre = self.increasingBST(root.left)\n",
    "            while pre.right:\n",
    "                pre = pre.right \n",
    "            pre.right = root \n",
    "            root.left = None \n",
    "            return cur \n",
    "        if root.right and root.left:\n",
    "            cur = pre = self.increasingBST(root.left)\n",
    "            nex = self.increasingBST(root.right)\n",
    "            while pre.right:\n",
    "                pre = pre.right \n",
    "            pre.right = root \n",
    "            root.left = None\n",
    "            root.right = nex\n",
    "            return cur "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.lst = []\n",
    "        def dg(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            dg(root.left)\n",
    "            self.lst.append(root.val)\n",
    "            dg(root.right)\n",
    "        dg(root)\n",
    "        root = TreeNode(self.lst[0])\n",
    "        head = root\n",
    "        for i in range(1,len(self.lst)):\n",
    "            root.right = TreeNode(self.lst[i])\n",
    "            root = root.right\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        inorder = []\n",
    "        while True:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            if not stack:\n",
    "                break \n",
    "            node = stack.pop()\n",
    "            inorder.append(node.val) \n",
    "            root = node.right \n",
    "        \n",
    "        dummy = TreeNode(-1)\n",
    "        cur = dummy\n",
    "        for val in inorder:\n",
    "            node = TreeNode(val)\n",
    "            cur.right = node\n",
    "            cur = cur.right\n",
    "        return dummy.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        # 先把左右子树拉平\n",
    "        left = self.increasingBST(root.left)\n",
    "        root.left = None\n",
    "        right = self.increasingBST(root.right)\n",
    "        # 这里要注意处理\n",
    "        root.right = right\n",
    "\n",
    "        # 左子树为空的话，就不用处理了\n",
    "        if not left:\n",
    "            return root \n",
    "        \n",
    "        # 左子树非空，需要把根节点和右子树接到左子树末尾\n",
    "        p = left\n",
    "        while p.right:\n",
    "            p = p.right\n",
    "        p.right = root \n",
    "\n",
    "        return left \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root):\n",
    "            path = []\n",
    "            stack = []\n",
    "            cur = root\n",
    "            while cur or stack:\n",
    "                if cur:\n",
    "                    stack.append(cur)\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    cur = stack.pop()\n",
    "                    path.append(cur.val)\n",
    "                    cur = cur.right\n",
    "            return path\n",
    "\n",
    "        path = dfs(root)\n",
    "        dummy_head = TreeNode(0)\n",
    "        prev = dummy_head\n",
    "        for val in path:\n",
    "            cur = TreeNode(val)\n",
    "            prev.right = cur\n",
    "            prev = cur\n",
    "        return dummy_head.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return None\n",
    "        self.dfs(root.left)\n",
    "        root.left = None\n",
    "        self.prev.right = root\n",
    "        self.prev = root\n",
    "        self.dfs(root.right)\n",
    "\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        dummy = TreeNode(-1)\n",
    "        self.prev = dummy\n",
    "        self.dfs(root)\n",
    "        return dummy.right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        nodes = []\n",
    "        def dfs(node):\n",
    "            nonlocal nodes\n",
    "            if not node:\n",
    "                return \n",
    "            dfs(node.left)\n",
    "            nodes += node,\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        ans = nodes[0]; pre = None\n",
    "        for n in nodes:\n",
    "            if pre:\n",
    "                pre.left = None\n",
    "                pre.right = n \n",
    "            pre = n\n",
    "            n.left = n.right = None\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        ans=[]\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            ans.append(node.val)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "\n",
    "        root1=TreeNode(ans[0])\n",
    "        ro=root1\n",
    "        for i in range(1,len(ans)):\n",
    "            ro.right=TreeNode(ans[i])\n",
    "            ro=ro.right\n",
    "        return root1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        sentinel = previous = TreeNode()\n",
    "\n",
    "        def dfs(node: TreeNode):\n",
    "            if not node:\n",
    "                return \n",
    "            dfs(node.left)\n",
    "\n",
    "            # 中序遍历部分\n",
    "            nonlocal previous\n",
    "            previous.right = node\n",
    "            node.left = None\n",
    "            previous = node\n",
    "\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return sentinel.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        lst =[]\n",
    "        def middle(node):\n",
    "            if node:\n",
    "                middle(node.left)\n",
    "                lst.append(node.val)\n",
    "                middle(node.right)\n",
    "        middle(root)\n",
    "        new_tree = TreeNode(lst[0])\n",
    "        new_tree_right =new_tree\n",
    "        for i in lst[1:]:\n",
    "            new_tree_cur = TreeNode(i)\n",
    "            new_tree_right.right = new_tree_cur\n",
    "            new_tree_right = new_tree_cur\n",
    "        return new_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        def middle(node):\n",
    "            if node:\n",
    "                middle(node.left)\n",
    "                stack.append(node.val)\n",
    "                middle(node.right)\n",
    "        middle(root)\n",
    "        newRoot = TreeNode(stack[0])\n",
    "        first = newRoot\n",
    "        for i in stack[1:]:\n",
    "            curr = TreeNode(i)\n",
    "            first.right = curr\n",
    "            first = curr\n",
    "        return newRoot       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.dummy = TreeNode()\n",
    "        self.prev = self.dummy\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            self.prev.right = root\n",
    "            root.left = None\n",
    "            self.prev = root\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.dummy.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(node, res):\n",
    "            if node:\n",
    "                dfs(node.left, res)\n",
    "                res.append(node)\n",
    "                dfs(node.right, res)\n",
    "            return res\n",
    "        res = dfs(root, [])\n",
    "        for i in range(1, len(res)):\n",
    "            res[i - 1].left = None\n",
    "            res[i - 1].right = res[i]\n",
    "        res[-1].left = None\n",
    "        return res[0]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums = []\n",
    "        def inorder(root):\n",
    "            if not root:return\n",
    "            if root.left:inorder(root.left)\n",
    "            nums.append(root.val)\n",
    "            if root.right:inorder(root.right)\n",
    "        inorder(root)\n",
    "        cur = ans = TreeNode(nums[0])\n",
    "        for i in range(1,len(nums)):\n",
    "            cur.right = TreeNode(nums[i])\n",
    "            cur = cur.right\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        self.res = None\n",
    "        self.qres = None\n",
    "\n",
    "        def dfs(p):\n",
    "            if(not p):\n",
    "                return\n",
    "            dfs(p.left)\n",
    "\n",
    "            if(self.res == None):\n",
    "                tem = TreeNode(p.val, None,None)\n",
    "                self.res = tem\n",
    "                self.qres = tem\n",
    "            else:\n",
    "                tem = TreeNode(p.val, None,None)\n",
    "                self.qres.right = tem\n",
    "                self.qres = self.qres.right\n",
    "\n",
    "            dfs(p.right)\n",
    "\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        queue = []\n",
    "        head = root\n",
    "        while head:\n",
    "            queue.append(head)\n",
    "            head = head.left\n",
    "        dummy = TreeNode()\n",
    "        head = dummy\n",
    "        \n",
    "        while queue:\n",
    "            a = queue.pop()\n",
    "            head.right = TreeNode(a.val)\n",
    "            head = head.right\n",
    "            if a.right:\n",
    "                a = a.right\n",
    "                while a:\n",
    "                    queue.append(a)\n",
    "                    a = a.left\n",
    "        \n",
    "        return dummy.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        ans=[]\n",
    "        def kkk(node):\n",
    "            if node:\n",
    "                kkk(node.left)\n",
    "                ans.append(node.val)\n",
    "                kkk(node.right)\n",
    "        kkk(root)\n",
    "        new_root=TreeNode(ans[0])\n",
    "        end=new_root\n",
    "        for i in ans[1:]:\n",
    "            curnode=TreeNode(i)\n",
    "            end.right=curnode\n",
    "            end=curnode\n",
    "        return new_root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        pre,ans = None,None\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return \n",
    "            dfs(root.left)\n",
    "            nonlocal pre\n",
    "            nonlocal ans\n",
    "            if pre is None:\n",
    "                ans = TreeNode(root.val)\n",
    "                pre = ans\n",
    "            else:\n",
    "                pre.right = TreeNode(root.val)\n",
    "                pre = pre.right\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return ans\n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        def dfs(r):\n",
    "            if not r:\n",
    "                return []\n",
    "            return dfs(r.left) + [r.val] + dfs(r.right)\n",
    "        \n",
    "        a = dfs(root)\n",
    "        h = c = TreeNode()\n",
    "        for i in a:\n",
    "            c.right = TreeNode(i)\n",
    "            c = c.right\n",
    "        return h.right\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "      head = node = TreeNode(0)\n",
    "      def dfs(root):\n",
    "        nonlocal node\n",
    "        if root:  \n",
    "          if root.left:\n",
    "            dfs(root.left)\n",
    "          node.right=TreeNode(root.val)\n",
    "          node = node.right\n",
    "          dfs(root.right)\n",
    "          \n",
    "            \n",
    "      dfs(root)\n",
    "      return head.right\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        lst = []\n",
    "        while stack or root:\n",
    "            # 不断往左走，每走一步将节点保存到栈中\n",
    "            if root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            # 当前节点为空，说明向左走到头了，从栈中弹出节点，并保存，然后向右走\n",
    "            else:\n",
    "                node = stack.pop()\n",
    "                lst.append(node)\n",
    "                root = node.right\n",
    "        lst[-1].left = None\n",
    "        lst[-1].right = None\n",
    "        for i in range(len(lst) - 1):\n",
    "            lst[i].left = None\n",
    "            lst[i].right = lst[i + 1]\n",
    "        return lst[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        dummyNode = TreeNode(-1)\n",
    "        self.resNode = dummyNode\n",
    "        def inorder(root):\n",
    "            if not root: return\n",
    "            inorder(root.left)\n",
    "            self.resNode.right = root\n",
    "            root.left = None\n",
    "            self.resNode = root\n",
    "            inorder(root.right)        \n",
    "        inorder(root)\n",
    "        return dummyNode.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        #传入子树的root节点，返回链表的起止节点\n",
    "        def dfs(root):\n",
    "            ret = [root, root]\n",
    "            if root.left:\n",
    "                (sLeft,lLeft) = dfs(root.left)\n",
    "                lLeft.right = root\n",
    "                ret[0] = sLeft\n",
    "                root.left = None\n",
    "            if root.right:\n",
    "                (sRight, lRight) = dfs(root.right)\n",
    "                root.right = sRight\n",
    "                ret[1] = lRight\n",
    "            return ret \n",
    "        \n",
    "        return dfs(root)[0]\n",
    "            \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def helper(root):\n",
    "    if not root: return None, None\n",
    "    l1, l2 = helper(root.left)\n",
    "    if l2: l2.right = root\n",
    "    root.left, root.right, r2 = None, *helper(root.right)\n",
    "    return (l1 if l1 else root, r2 if r2 else root)\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        return helper(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.virtual_root = TreeNode(0)\n",
    "        ans = self.virtual_root\n",
    "        self.tip = None\n",
    "        def dfs(node):\n",
    "            if node == None:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            self.tip = node\n",
    "            self.virtual_root.right = self.tip\n",
    "            self.virtual_root = self.virtual_root.right\n",
    "            self.virtual_root.left = None\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return ans.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def func(node):    # 返回 node 重排后的 lnode 和 rnode\n",
    "            if not node.left and not node.right:\n",
    "                return node, node\n",
    "            if not node.left and node.right:\n",
    "                rb, rs = func(node.right)\n",
    "                node.right = rb\n",
    "                return node, rs\n",
    "            if node.left and not node.right:\n",
    "                lb, ls = func(node.left)\n",
    "                node.left = None\n",
    "                ls.right = node\n",
    "                return lb, node\n",
    "            lb, ls = func(node.left)\n",
    "            rb, rs = func(node.right)\n",
    "            ls.right = node\n",
    "            node.left = None\n",
    "            node.right = rb\n",
    "            return lb, rs\n",
    "        \n",
    "        return func(root)[0]\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        # 二叉搜索树的中序有序性\n",
    "        def mid(root):\n",
    "            if not root:\n",
    "                return\n",
    "            mid(root.left)\n",
    "            self.ans.right = TreeNode(root.val)\n",
    "            self.ans = self.ans.right\n",
    "            mid(root.right)\n",
    "        newroot = TreeNode()\n",
    "        self.ans = newroot\n",
    "        mid(root)\n",
    "        return newroot.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        def DFS(root):\n",
    "            if not root: return\n",
    "            DFS(root.left)\n",
    "            self.newtree.right = TreeNode(root.val)\n",
    "            self.newtree = self.newtree.right\n",
    "            DFS(root.right)\n",
    "\n",
    "        newTreeHEAD = TreeNode()\n",
    "        self.newtree = newTreeHEAD\n",
    "        DFS(root)\n",
    "        return newTreeHEAD.right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST1(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        res = []\n",
    "        def process(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            \n",
    "            process(node.left)\n",
    "            res.append(node)\n",
    "            process(node.right)\n",
    "        \n",
    "\n",
    "        process(root)\n",
    "        dummy = TreeNode(-1)\n",
    "        cur = dummy\n",
    "        for n in res:\n",
    "            cur.right = TreeNode(n.val)\n",
    "            cur = cur.right\n",
    "        \n",
    "        return dummy.right\n",
    "\n",
    "    \n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        def process(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            nonlocal pre\n",
    "            process(node.left)\n",
    "            pre.right = node \n",
    "            node.left = None\n",
    "            pre = node\n",
    "            process(node.right)\n",
    "        \n",
    "        dummy = TreeNode(-1)\n",
    "        pre = dummy\n",
    "        process(root)\n",
    "        \n",
    "        return dummy.right\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        ans = TreeNode(0)\n",
    "        i = ans\n",
    "        stack = []\n",
    "        while root or len(stack) > 0:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "            i.right = TreeNode(root.val)\n",
    "            i = i.right\n",
    "            root = root.right\n",
    "        return ans.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inOrder(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        self.res.append(root)\n",
    "        self.inOrder(root.right)\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.res = list()\n",
    "        self.inOrder(root)\n",
    "        if not self.res:\n",
    "            return\n",
    "        dummy = TreeNode(-1)\n",
    "        cur = dummy\n",
    "        for node in self.res:\n",
    "            node.left = node.right = None\n",
    "            cur.right = node\n",
    "            cur = cur.right\n",
    "        return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:        \n",
    "        def qfs(root):\n",
    "            queue=[root]\n",
    "            r=[]\n",
    "            while queue:\n",
    "                a=queue.pop()\n",
    "                if a.left:\n",
    "                    queue.append(a.left)   \n",
    "                if a.right:\n",
    "                    queue.append(a.right) \n",
    "                if a :          \n",
    "                    r.append(a.val)            \n",
    "            return r\n",
    "        res=[]\n",
    "        def dfs(root,res):\n",
    "            if not root:\n",
    "                return []\n",
    "            if root.left:                \n",
    "                dfs(root.left,res)\n",
    "            res.append(root.val)\n",
    "            if root.right:\n",
    "                dfs(root.right,res)\n",
    "        dfs(root,res)\n",
    "        \n",
    "        #print(res)\n",
    "        rr=TreeNode(res.pop(0))\n",
    "        new=rr\n",
    "        while res:\n",
    "            t=TreeNode(res.pop(0))\n",
    "            new.right=t\n",
    "            new=t\n",
    "        #print(rr)\n",
    "        return rr\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root: TreeNode):\n",
    "            if root is None:\n",
    "                return\n",
    "\n",
    "            dfs(root.left)\n",
    "\n",
    "            nonlocal cur\n",
    "            cur.right = root\n",
    "            root.left = None\n",
    "            cur = cur.right\n",
    "\n",
    "            dfs(root.right)\n",
    "\n",
    "        cur = dummy = TreeNode()\n",
    "        dfs(root)\n",
    "        return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def f(root):\n",
    "            if root:\n",
    "                l_small = r_large = root\n",
    "                if root.left:\n",
    "                    l_small, l_large = f(root.left)\n",
    "                    l_large.right = root\n",
    "                    root.left = None\n",
    "                if root.right:\n",
    "                    r_small, r_large = f(root.right)\n",
    "                    root.right = r_small\n",
    "                return l_small, r_large\n",
    "        ans = f(root)[0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(node: TreeNode, ans: List[int]):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left, ans)\n",
    "            ans.append(node.val)\n",
    "            dfs(node.right, ans)\n",
    "        nums, ans, temp = [], None, None\n",
    "        dfs(root, nums)\n",
    "        for num in nums:\n",
    "            if not temp:\n",
    "                ans = TreeNode(num)\n",
    "                temp = ans\n",
    "            else:\n",
    "                temp.right = TreeNode(num)\n",
    "                temp = temp.right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        list=[]               #不需要加self，也可以在子函数中使用。\n",
    "\n",
    "        def dfs(root):\n",
    "          if not root: return\n",
    "          dfs(root.left)\n",
    "          list.append(root)\n",
    "          dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "    #构建递增顺序搜索树\n",
    "        dummy=TreeNode()\n",
    "        cur=dummy\n",
    "        for node in list:\n",
    "            cur.right=node\n",
    "            cur=node\n",
    "            cur.left=None\n",
    "        return dummy.right\n",
    "        \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(node, array):\n",
    "            if node == None:\n",
    "                return\n",
    "            dfs(node.left,array)\n",
    "            array.append(node.val)\n",
    "            dfs(node.right,array)\n",
    "        nodeval = []\n",
    "        dfs(root, nodeval)\n",
    "        newroot = TreeNode()\n",
    "        node, index = newroot, 0\n",
    "        while index < len(nodeval)-1:\n",
    "            node.val = nodeval[index]\n",
    "            node.right = TreeNode()\n",
    "            node = node.right\n",
    "            index += 1\n",
    "        node.val = nodeval[index]\n",
    "        return newroot\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(r):\n",
    "            nonlocal pre, ans\n",
    "            if not r:\n",
    "                return\n",
    "            dfs(r.left)\n",
    "            r.left = None\n",
    "            if pre:\n",
    "                pre.right = r\n",
    "            if pre is None:\n",
    "                ans = r\n",
    "            pre = r\n",
    "            dfs(r.right)\n",
    "\n",
    "        pre, ans = None, None\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        newTree = None\n",
    "        pre = None\n",
    "        def traversal(root) -> None:\n",
    "            nonlocal newTree, pre\n",
    "            if not root:\n",
    "                return \n",
    "            traversal(root.left)\n",
    "            if not newTree:\n",
    "                newTree = TreeNode(root.val)\n",
    "                pre = newTree\n",
    "            else:\n",
    "                pre.right = TreeNode(root.val)\n",
    "                pre = pre.right\n",
    "            traversal(root.right)\n",
    "        traversal(root)\n",
    "        return newTree\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        def flatten(node: TreeNode) -> (TreeNode, TreeNode):\n",
    "            if not node.left and not node.right:\n",
    "                return node, node\n",
    "            head, tail = node, node\n",
    "            if node.left:\n",
    "                left_head, left_tail = flatten(node.left)\n",
    "                node.left = None\n",
    "                left_tail.right = node\n",
    "                head = left_head\n",
    "            if node.right:\n",
    "                right_head, right_tail = flatten(node.right)\n",
    "                node.right = right_head\n",
    "                tail = right_tail\n",
    "\n",
    "            return head, tail\n",
    "        \n",
    "        return flatten(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root, res):\n",
    "        if not root:\n",
    "            return None\n",
    "        self.dfs(root.left, res)\n",
    "        res.append(root)\n",
    "        self.dfs(root.right, res)\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        res = []\n",
    "        self.dfs(root, res)\n",
    "        if not res:\n",
    "            return None\n",
    "        dummy = TreeNode(-1)\n",
    "        cur = dummy\n",
    "        for node in res:\n",
    "            node.left = node.right = None\n",
    "            cur.right = node\n",
    "            cur = cur.right\n",
    "        return dummy.right\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        tmp=[]\n",
    "        def helper(node):\n",
    "            if not node.left and not node.right:\n",
    "                tmp.append(node)\n",
    "                return\n",
    "            if node.left:\n",
    "                helper(node.left)\n",
    "            tmp.append(node)\n",
    "            if node.right:\n",
    "                helper(node.right)\n",
    "        helper(root)\n",
    "        tmp[-1].right = None\n",
    "        tmp[-1].left=None\n",
    "        def he(node1,node2):\n",
    "            node2.right = node1\n",
    "            node2.left=None\n",
    "            return node2\n",
    "\n",
    "        return reduce(he,tmp[::-1])\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        dummyNode=TreeNode(-1)\n",
    "        resNode=dummyNode\n",
    "        \n",
    "        def inorder(node: TreeNode):\n",
    "            if node is None:\n",
    "                return\n",
    "            nonlocal resNode\n",
    "            inorder(node.left)\n",
    "            resNode.right=node\n",
    "            node.left=None\n",
    "            resNode=node\n",
    "            inorder(node.right)\n",
    "        inorder(root)\n",
    "        return dummyNode.right\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(aRt):\n",
    "            if aRt:\n",
    "                h, t = dfs(aRt.left)\n",
    "                if h != None:\n",
    "                    t.right = aRt\n",
    "                    aRt.left = None\n",
    "                    t = aRt\n",
    "                else:\n",
    "                    h = aRt\n",
    "                    t = aRt\n",
    "                h1, t1 = dfs(aRt.right)\n",
    "                if h1 != None:\n",
    "                    aRt.right = None\n",
    "                    t.right = h1\n",
    "                    t = t1\n",
    "                else:\n",
    "                    t = aRt\n",
    "                return h, t\n",
    "            else:\n",
    "                return None, None\n",
    "        h, t = dfs(root)\n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def middle_order_traversal(node: TreeNode, _list: []) -> None:\n",
    "            if node.left != None:\n",
    "                middle_order_traversal(node.left, _list)\n",
    "            _list.append(node)\n",
    "            if node.right != None:\n",
    "                middle_order_traversal(node.right, _list)\n",
    "            return\n",
    "        \n",
    "        node = None\n",
    "\n",
    "        if root != None:\n",
    "            _list = []\n",
    "            middle_order_traversal(root, _list)\n",
    "            \n",
    "            while _list:\n",
    "                tmp = _list.pop(-1)\n",
    "                tmp.left = None\n",
    "                tmp.right = node\n",
    "                node = tmp\n",
    "\n",
    "        return node"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
